package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位
 */

public class NQueens {
    class Solution {
        List<List<String>> res = new ArrayList<>();

        public List<List<String>> solveNQueens(int n) {
            char[][] board = new char[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    board[i][j] = '.';
            }

            backtracking(board, 0);
            return res;
        }

        private void backtracking(char[][] board, int row) {
            if (row == board.length) {
                res.add(transfer(board));
                return;
            }

            for (int j = 0; j < board.length; j++) {
                if (check(board, row, j)) {
                    board[row][j] = 'Q';
                    backtracking(board, row + 1);
                    board[row][j] = '.';
                }
            }
        }

        private List<String> transfer(char[][] board) {
            List<String> res = new ArrayList<>();
            for (int i = 0; i < board.length; i++) {
                StringBuilder sb = new StringBuilder();
                for (char c : board[i])
                    sb.append(c);
                res.add(sb.toString());
            }
            return res;
        }

        private boolean check(char[][] board, int i, int j) {
            // 同一列
            for (int row = 0; row < i; row++)
                if (board[row][j] == 'Q') return false;
            // 45对角线
            for (int row = i - 1, col = j + 1; row >= 0 && col < board.length; row--, col++)
                if (board[row][col] == 'Q') return false;
            // 135对角线
            for (int row = i - 1, col = j - 1; row >= 0 && col >= 0; row--, col--)
                if (board[row][col] == 'Q') return false;
            return true;
        }
    }
}
